package com.huawei.od;

import java.util.*;

/**
 * 862. 和至少为 K 的最短子数组
 * 队列
 */
public class TestFive {

    public static void main(String[] args) {
        System.out.println(shortestSubarray(new int[]{2, -1, 2}, 3));
    }

    public static int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] preSumArray = new long[n + 1];
        for (int i = 0; i < n; i++) {
            preSumArray[i + 1] = preSumArray[i] + nums[i];
        }
        int res = n + 1;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            long curSum = preSumArray[i];
            while (!queue.isEmpty() && curSum - preSumArray[queue.peekFirst()] >= k) {
                res = Math.min(res, i - queue.pollFirst());
            }
            while (!queue.isEmpty() && preSumArray[queue.peekLast()] >= curSum) {
                queue.pollLast();
            }
            queue.offerLast(i);
        }
        return res < n + 1 ? res : -1;
    }
}
